﻿// --------------------------------------------------------------------------------------------------------------------
// <copyright file="MinHeap.cs" company="pwasiewicz">
//   pwasiewicz
// </copyright>
// <summary>
//   Defines the MinHeap type.
// </summary>
// --------------------------------------------------------------------------------------------------------------------

namespace LogicSystem.Helpers
{
    using System;
    using System.Collections.Generic;

    /// <summary>The min heap.</summary>
    /// <typeparam name="TK">The key type.</typeparam>
    /// <typeparam name="TV">The value type.</typeparam>
    public class MinHeap<TK, TV> where TK : IComparable<TK>
    {

        /// <summary>The heap.</summary>
        private readonly List<KeyValuePair<TK, TV>> heap;

        /// <summary>Initializes a new instance of the <see cref="MinHeap{TK,TV}"/> class. 
        /// Initializes a new instance of Minimum Heap.</summary>
        public MinHeap()
        {
            this.heap = new List<KeyValuePair<TK, TV>>();
        }


        /// <summary>
        /// Inserts new element into heap.
        /// </summary>
        /// <param name="key">The key.</param>
        /// <param name="value">The value.</param>
        public void Insert(TK key, TV value)
        {
            this.heap.Add(new KeyValuePair<TK, TV>(key, value));
            this.CascadeUp(this.heap.Count - 1);
        }

        /// <summary>
        /// Inserts collection of key-values pairs into heap.
        /// </summary>
        /// <param name="items">Collection of key-value pairs.</param>
        public void Insert(IEnumerable<KeyValuePair<TK, TV>> items)
        {
            foreach (var item in items)
            {
                this.Insert(item.Key, item.Value);
            }
        }

        /// <summary>
        /// Removes top element of heap.
        /// </summary>
        /// <returns>Removed key-value pair (lowest key value).</returns>
        public KeyValuePair<TK, TV> Remove()
        {
            var node = this.heap[0];
            this.heap[0] = this.heap[this.heap.Count - 1];
            this.heap.RemoveAt(this.heap.Count - 1);

            if (this.heap.Count > 0)
            {
                this.CascadeDown(0);
            }

            return node;
        }

        /// <summary>
        /// Gets element from the heap top.
        /// </summary>
        /// <returns>Element that key values is lowest.</returns>
        public KeyValuePair<TK, TV> Top()
        {
            return this.heap[0];
        }

        /// <summary>
        /// Checks if heap is empty.
        /// </summary>
        /// <returns>True, if heap is empty, false otherwise.</returns>
        public bool IsEmpty()
        {
            return this.heap.Count == 0;
        }

        /// <summary>
        /// Clears whole heap.
        /// </summary>
        internal void Clear()
        {
            this.heap.Clear();
        }

        /// <summary>
        /// Flushes element at specified index up in
        /// order to preserve heap.
        /// </summary>
        /// <param name="index">The element index.</param>
        protected void CascadeUp(int index)
        {
            var node = this.heap[index];

            var parent = (index - 1) / 2;
            while (index > 0 && this.heap[parent].Key.CompareTo(
                                    this.heap[index].Key) > 0)
            {
                this.heap[index] = this.heap[parent];
                index = parent;
                parent = (parent - 1) / 2;
            }

            this.heap[index] = node;
        }

        /// <summary>
        /// Flushes element at specified index down in
        /// other to preserve heap.
        /// </summary>
        /// <param name="index">The element index.</param>
        protected void CascadeDown(int index)
        {
            var node = this.heap[0];

            while (index < this.heap.Count / 2)
            {
                var leftChild = (2 * index) + 1;
                var rightChild = leftChild + 1;

                var smallerChild = rightChild < this.heap.Count &&
                                   this.heap[leftChild].Key.CompareTo(this.heap[rightChild].Key) > 0 ?
                                       rightChild : leftChild;

                if (node.Key.CompareTo(this.heap[smallerChild].Key) < 0)
                {
                    break;
                }

                this.heap[index] = this.heap[smallerChild];
                index = smallerChild;
            }

            this.heap[index] = node;
        }
    }
}
